package com.pointstar.dp.tree;

/**
 * 南软2006T1、2015T1
 * 递归计算二叉树高度
 *
 * @author 朱科睿
 */
public class TreeHeight {

    public static void main(String[] args) {
        BinaryTree third1 = new BinaryTree(4);
        BinaryTree third3 = new BinaryTree(6);
        BinaryTree second2 = new BinaryTree(3);
        second2.setFirstChild(third3);
        BinaryTree second1 = new BinaryTree(2);
        second1.setFirstChild(third1);
        second1.setNextSibling(second2);
        BinaryTree root = new BinaryTree(1);
        root.setFirstChild(second1);

        System.out.println("二叉树高度: " + getHeightOfTree(root, 0));
    }

    /**
     * 递归计算二叉树高度
     *
     * @param root 二叉树根节点
     * @return 二叉树高度
     */
    private static int getHeightOfTree(BinaryTree root, int currentHeight) {
        if (root != null) {
            return Math.max(getHeightOfTree(root.nextSibling, currentHeight),
                    getHeightOfTree(root.firstChild, ++currentHeight));
        }
        return currentHeight;
    }

    /**
     * 二叉树
     */
    static class BinaryTree {

        private final int data;
        BinaryTree firstChild;
        BinaryTree nextSibling;

        public BinaryTree(int data) {
            this.data = data;
        }

        public void setFirstChild(BinaryTree firstChild) {
            this.firstChild = firstChild;
        }

        public void setNextSibling(BinaryTree nextSibling) {
            this.nextSibling = nextSibling;
        }

    }

}
